/*
 * @(#)FourColor.java
 * Four color problem
 * See Martin Gardner: Mathematical Games, Scientific American, April, 1975.
 */
import jp.ac.kobe_u.cs.cream.*;
import java.awt.*;
import java.awt.event.*;

public class FourColor extends Frame {
    static int map[][] = {
	{  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1},
	{  2,  2,  3,  3,  3,  3,  4,  4,  4,  4,  5,  5,  5,  5,  6,  6,  6,  6,  7,  7,  7,  7,  8,  8,  8,  8,  9,  9,  9,  9, 10, 10, 10, 10, 11, 11,  1},
	{  2, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19, 20, 20, 20, 11,  1},
	{  2, 12, 12, 21, 21, 21, 22, 22, 22, 22, 23, 23, 23, 23, 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 27, 27, 27, 27, 28, 28, 28, 20, 20, 11,  1},
	{  2, 12, 12, 21, 21, 29, 29, 29, 30, 30, 30, 30, 31, 31, 31, 31, 32, 32, 32, 32, 33, 33, 33, 33, 34, 34, 34, 34, 35, 35, 35, 28, 28, 20, 20, 11,  1},
	{  2, 12, 12, 21, 21, 29, 29, 36, 36, 36, 37, 37, 37, 37, 38, 38, 38, 38, 39, 39, 39, 39, 40, 40, 40, 40, 41, 41, 41, 35, 35, 28, 28, 20, 20, 11,  1},
	{  2, 12, 12, 21, 21, 29, 29, 36, 36, 42, 42, 42, 43, 43, 43, 43, 44, 44, 44, 44, 45, 45, 45, 45, 46, 46, 46, 41, 41, 35, 35, 28, 28, 20, 20, 11,  1},
	{  2, 12, 12, 21, 21, 29, 29, 36, 36, 42, 42, 47, 47, 47, 48, 48, 48, 48, 49, 49, 49, 49, 50, 50, 50, 46, 46, 41, 41, 35, 35, 28, 28, 20, 20, 11,  1},
	{  2, 12, 12, 21, 21, 29, 29, 36, 36, 42, 42, 47, 47, 51, 51, 51, 52, 52, 52, 52, 53, 53, 53, 50, 50, 46, 46, 41, 41, 35, 35, 28, 28, 20, 20, 11,  1},
	{  2, 12, 12, 21, 21, 29, 29, 36, 36, 42, 42, 47, 47, 51, 51, 54, 54, 54, 55, 55, 55, 53, 53, 50, 50, 46, 46, 41, 41, 35, 35, 28, 28, 20, 20, 11,  1},
	{  2, 12, 12, 21, 21, 29, 29, 36, 36, 42, 42, 47, 47, 51, 51, 54, 54, 56, 56, 55, 55, 53, 53, 50, 50, 46, 46, 41, 41, 35, 35, 28, 28, 20, 20, 11,  1},
	{  2, 57, 58, 58, 59, 59, 60, 60, 61, 61, 62, 62, 63, 63, 64, 64, 65, 56, 56, 66, 67, 67, 68, 68, 69, 69, 70, 70, 71, 71, 72, 72, 73, 73,  1,  1,  1},
	{  2, 57, 58, 58, 59, 59, 60, 60, 61, 61, 62, 62, 63, 63, 64, 64, 65, 65, 66, 66, 67, 67, 68, 68, 69, 69, 70, 70, 71, 71, 72, 72, 73, 73,  1,  1,  1},
	{  2, 57, 58, 58, 59, 59, 60, 60, 61, 61, 62, 62, 63, 63, 64, 64, 64, 74, 74, 67, 67, 67, 68, 68, 69, 69, 70, 70, 71, 71, 72, 72, 73, 73,  1,  1,  1},
	{  2, 57, 58, 58, 59, 59, 60, 60, 61, 61, 62, 62, 63, 63, 63, 75, 75, 75, 76, 76, 76, 68, 68, 68, 69, 69, 70, 70, 71, 71, 72, 72, 73, 73,  1,  1,  1},
	{  2, 57, 58, 58, 59, 59, 60, 60, 61, 61, 62, 62, 62, 77, 77, 77, 77, 78, 78, 79, 79, 79, 79, 69, 69, 69, 70, 70, 71, 71, 72, 72, 73, 73,  1,  1,  1},
	{  2, 57, 58, 58, 59, 59, 60, 60, 61, 61, 61, 80, 80, 80, 80, 81, 81, 81, 82, 82, 82, 83, 83, 83, 83, 70, 70, 70, 71, 71, 72, 72, 73, 73,  1,  1,  1},
	{  2, 57, 58, 58, 59, 59, 60, 60, 60, 84, 84, 84, 84, 85, 85, 85, 85, 86, 86, 87, 87, 87, 87, 88, 88, 88, 88, 71, 71, 71, 72, 72, 73, 73,  1,  1,  1},
	{  2, 57, 58, 58, 59, 59, 59, 89, 89, 89, 89, 90, 90, 90, 90, 91, 91, 91, 92, 92, 92, 93, 93, 93, 93, 94, 94, 94, 94, 72, 72, 72, 73, 73,  1,  1,  1},
	{  2, 57, 58, 58, 58, 95, 95, 95, 95, 96, 96, 96, 96, 97, 97, 97, 97, 98, 98, 99, 99, 99, 99,100,100,100,100,101,101,101,101, 73, 73, 73,  1,  1,  1},
	{  2, 57, 57,102,102,102,102,103,103,103,103,104,104,104,104,105,105,105,106,106,106,107,107,107,107,108,108,108,108,109,109,109,109,  1,  1,  1,  1},
	{  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2}
    };
    static int neighbors[][] = {
	{1, 2,3,4,5,6,7,8,9,10,11,20,73,109,110},
	{2, 1,3,12,57,102,103,104,105,106,110},
	{3, 1,2,4,12,13},
	{4, 1,3,5,13,14},
	{5, 1,4,6,14,15},
	{6, 1,5,7,15,16},
	{7, 1,6,8,16,17},
	{8, 1,7,9,17,18},
	{9, 1,8,10,18,19},
	{10, 1,9,11,19,20},
	{11, 1,10,20},
	{12, 2,3,13,21,57,58},
	{13, 3,4,12,14,21,22},
	{14, 4,5,13,15,22,23},
	{15, 5,6,14,16,23,24},
	{16, 6,7,15,17,24,25},
	{17, 7,8,16,18,25,26},
	{18, 8,9,17,19,26,27},
	{19, 9,10,18,20,27,28},
	{20, 1,10,11,19,28,73},
	{21, 12,13,22,29,58,59},
	{22, 13,14,21,23,29,30},
	{23, 14,15,22,24,30,31},
	{24, 15,16,23,25,31,32},
	{25, 16,17,24,26,32,33},
	{26, 17,18,25,27,33,34},
	{27, 18,19,26,28,34,35},
	{28, 19,20,27,35,72,73},
	{29, 21,22,30,36,59,60},
	{30, 22,23,29,31,36,37},
	{31, 23,24,30,32,37,38},
	{32, 24,25,31,33,38,39},
	{33, 25,26,32,34,39,40},
	{34, 26,27,33,35,40,41},
	{35, 27,28,34,41,71,72},
	{36, 29,30,37,42,60,61},
	{37, 30,31,36,38,42,43},
	{38, 31,32,37,39,43,44},
	{39, 32,33,38,40,44,45},
	{40, 33,34,39,41,45,46},
	{41, 34,35,40,46,70,71},
	{42, 36,37,43,47,61,62},
	{43, 37,38,42,44,47,48},
	{44, 38,39,43,45,48,49},
	{45, 39,40,44,46,49,50},
	{46, 40,41,45,50,69,70},
	{47, 42,43,48,51,62,63},
	{48, 43,44,47,49,51,52},
	{49, 44,45,48,50,52,53},
	{50, 45,46,49,53,68,69},
	{51, 47,48,52,54,63,64},
	{52, 48,49,51,53,54,55},
	{53, 49,50,52,55,67,68},
	{54, 51,52,55,56,64,65},
	{55, 52,53,54,56,66,67},
	{56, 54,55,65,66},
	{57, 2,12,58,102},
	{58, 12,21,57,59,95,102},
	{59, 21,29,58,60,89,95},
	{60, 29,36,59,61,84,89},
	{61, 36,42,60,62,80,84},
	{62, 42,47,61,63,77,80},
	{63, 47,51,62,64,75,77},
	{64, 51,54,63,65,74,75},
	{65, 54,56,64,66,74},
	{66, 55,56,65,67,74},
	{67, 53,55,66,68,74,76},
	{68, 50,53,67,69,76,79},
	{69, 46,50,68,70,79,83},
	{70, 41,46,69,71,83,88},
	{71, 35,41,70,72,88,94},
	{72, 28,35,71,73,94,101},
	{73, 1,20,28,72,101,109},
	{74, 64,65,66,67,75,76},
	{75, 63,64,74,76,77,78},
	{76, 67,68,74,75,78,79},
	{77, 62,63,75,78,80,81},
	{78, 75,76,77,79,81,82},
	{79, 68,69,76,78,82,83},
	{80, 61,62,77,81,84,85},
	{81, 77,78,80,82,85,86},
	{82, 78,79,81,83,86,87},
	{83, 69,70,79,82,87,88},
	{84, 60,61,80,85,89,90},
	{85, 80,81,84,86,90,91},
	{86, 81,82,85,87,91,92},
	{87, 82,83,86,88,92,93},
	{88, 70,71,83,87,93,94},
	{89, 59,60,84,90,95,96},
	{90, 84,85,89,91,96,97},
	{91, 85,86,90,92,97,98},
	{92, 86,87,91,93,98,99},
	{93, 87,88,92,94,99,100},
	{94, 71,72,88,93,100,101},
	{95, 58,59,89,96,102,103},
	{96, 89,90,95,97,103,104},
	{97, 90,91,96,98,104,105},
	{98, 91,92,97,99,105,106},
	{99, 92,93,98,100,106,107},
	{100, 93,94,99,101,107,108},
	{101, 72,73,94,100,108,109},
	{102, 2,57,58,95,103},
	{103, 2,95,96,102,104},
	{104, 2,96,97,103,105},
	{105, 2,97,98,104,106},
	{106, 2,98,99,105,107,110},
	{107, 99,100,106,108,110},
	{108, 100,101,107,109,110},
	{109, 1,73,101,108,110},
	{110, 1,2,106,107,108,109}
    };
    FourColorPanel fourColorPanel;
    Button nextButton;
    Button quitButton;
    static int WAIT = 0;
    static int NEXT = 1;
    static int QUIT = 2;
    int state = WAIT;

    public FourColor(int map[][]) {
	setSize(400, 400);
	setLayout(new BorderLayout());
	fourColorPanel = new FourColorPanel(map);
	add("Center", fourColorPanel);
	Panel p = new Panel();
	nextButton = new Button("Next");
	nextButton.addActionListener(new ActionListener() {
	    public void actionPerformed(ActionEvent e) { actionNext(); }
	});
	quitButton = new Button("Quit");
	quitButton.addActionListener(new ActionListener() {
	    public void actionPerformed(ActionEvent e) { actionQuit(); }
	});
	p.add(nextButton);
	p.add(quitButton);
	add("South", p);
	validate();
	show();
    }

    private void setSolution(Solution solution, IntVariable region[]) {
	int n = region.length;
	int color[] = new int[n+1];
	for (int i = 0; i < n; i++) {
	    IntDomain d = (IntDomain)solution.getDomain(region[i]);
	    if (d.size() == 1) {
		color[i+1] = d.value();
	    } else {
		color[i+1] = 0;
	    }
	}
	fourColorPanel.setColor(color);
	fourColorPanel.repaint();
    }

    private synchronized void setStateWait() {
	state = WAIT;
    }

    private synchronized void actionNext() {
	state = NEXT;
	notifyAll();
    }

    private synchronized void actionQuit() {
	state = QUIT;
	notifyAll();
    }

    private synchronized void waitAction() {
	while (state == WAIT) {
	    try {
		wait();
	    } catch (InterruptedException e) {}
	}
    }

    public void paint(Graphics g) {
	paintComponents(g);
    }

    public static void main(String args[]) {
	FourColor fc = new FourColor(map);

	Network net = new Network();
	int n = neighbors.length;
	IntVariable region[] = new IntVariable[n];

	for (int i = 0; i < n; i++)
	    region[i] = new IntVariable(net, 1, 4);
	for (int i = 0; i < n; i++) {
	    IntVariable v = region[neighbors[i][0] - 1];
	    for (int j = 1; j < neighbors[i].length; ++j)
		if (neighbors[i][0] < neighbors[i][j])
		    v.notEquals(region[neighbors[i][j] - 1]);
	}
	Solver solver = new DefaultSolver(net);
	solver.start();
	while (true) {
	    fc.setStateWait();
	    fc.waitAction();
	    if (fc.state == QUIT)
		break;
	    if (! solver.waitNext())
		break;
	    fc.setSolution(solver.getSolution(), region);
	    solver.resume();
	}
	solver.stop();
	fc.dispose();
    }

}

class FourColorPanel extends Panel {
    int map[][] = null;
    int color[] = null;
    Color ct[] = {Color.lightGray, Color.white, Color.orange, Color.cyan, Color.green};

    FourColorPanel(int m[][]) {
	map = m;
    }

    public synchronized void setColor(int c[]) {
	color = c;
    }

    public void paint(Graphics g) {
	if (map == null)
	  return;
	int h = getSize().height - 10;
	int w = getSize().width - 10;
	int M = map.length;
	int N = map[0].length;
	int cell_h = h/M;
	int cell_w = w/N;
	int y0 = (getSize().height - M*cell_h)/2;
	int x0 = (getSize().width - N*cell_w)/2;
	int x, y, c;
	if (color != null) {
	    for (int i = 0; i < M; ++i) {
		for (int j = 0; j < N; ++j) {
		    x = x0 + j*cell_w;
		    y = y0 + i*cell_h;
		    c = color[map[i][j]];
		    g.setColor(ct[c]);
		    g.fillRect(x, y, cell_w, cell_h);
		}
	    }
	}
	g.setColor(Color.black);
	g.drawRect(x0, y0, N*cell_w, M*cell_h);
	for (int i = 0; i < M; ++i) {
	    for (int j = 0; j < N; ++j) {
		x = x0 + j*cell_w;
		y = y0 + i*cell_h;
		if (i < M-1 && map[i][j] != map[i+1][j]) {
		    g.drawLine(x, y+cell_h, x+cell_w, y+cell_h);
		}
		if (j < N-1 && map[i][j] != map[i][j+1]) {
		    g.drawLine(x+cell_w, y, x+cell_w, y+cell_h);
		}
	    }
	}
    }
    
}
